/*
* 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
* */
public class HasSubtree {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public boolean hasSubtree(TreeNode root1,TreeNode root2) {
        boolean result=false;  //设置匹配标志位，匹配成功设为true
        if(root1!=null && root2!=null){  //仅当root1和root2不为空树时比较，否则直接返回false
            if(root1.val==root2.val){  //当二叉树root1和root2的根节点值相同时，比较它们的子树是否完全一致
                result=doesTree1HasTree2(root1,root2);
            }
            if(!result){  //如果在root1的根节点处没有找到和root2根节点的值相同的节点，递归查找root1的左子树里是否有和root2根节点的值相同的节点
                result=hasSubtree(root1.left,root2);
            }
            if(!result){  //如果在root1的左子树中没有找到和root2根节点的值相同的节点，递归查找root1的右子树里是否有和root2根节点的值相同的节点
                result=hasSubtree(root1.right,root2);
            }
        }
        return result;
    }

    public boolean doesTree1HasTree2(TreeNode root1,TreeNode root2){
        if(root2==null){  //如果二叉树root2已经被遍历完，此时root1不管有没有遍历完，都说明匹配，二叉树root2是root1的子树
            return true;
        }
        if(root1==null && root2!=null){  //如果二叉树root1已经被遍历完，而root2没有被遍历完，说明root1里不包含root2
            return false;
        }
        if(root1.val!=root2.val){  //在递归遍历的比较过程中，也许root1中某个子树前面一些节点与root2的前面一些节点一致，但只要有中间一个节点的值不一致，说明root2不是root1的子树
            return false;
        }
        return doesTree1HasTree2(root1.left,root2.left) && doesTree1HasTree2(root1.right,root2.right);  //在root1当前子树根节点与root2根节点值相同时，递归比较它们的左子树和右子树是否都一致
    }
}
